剑指offer 38——字符串的排列

发表于 | 分类于 | 阅读次数:

本题主要在于对回溯的理解，优化时可以结合 java 特性，以及排列的一些知识。

原题

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

1
2
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

限制：

1
1 <= s 的长度 <= 8

原题url：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof

解题

回溯

回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

大家在解决经典的八皇后问题时，大多都会采用回溯进行解决。

本问题其实就是求所有字符的排列组合，针对这种问题，也可以利用回溯进行解决，但要求不能重复，因此需要进行剪枝。

比如字符串 abc ，如果让我们求所有排列，肯定是：

  1. 先固定第 1 位，从 a 、b 、 c 中选一个，比如 a。
  2. 在以 a 为第 1 位的前提下，固定第 2 位，从 b 、 c 中选一个，比如 b。
  3. 此时第 3 位也没有可以选择的余地了，只剩下 c，这一步就走完了。
  4. 退回第 2 步，依旧在第 2 位，这次选择 c 。
  5. 此时第 3 位也没有可以选择的余地了，只剩下 b，这一步也走完了。
  6. 退回第 1 步。

从上面，你可以总结出，正常的回溯，就是先走一条路，当结束后，退回上一步继续走，反复执行，直至退无可退，结束流程。

我们可以发现，最终是没有可以选择的余地，这在程序里可以理解为，运行到下一位时，不能使用之前使用过的数据，因此会涉及到字符交换。

但因为会进行回溯，所以数字可以在回溯后再换回去，从而不影响下一次的回溯。

那什么叫剪枝呢？就是要排除一些情况，针对本题，就是要排除重复的情况。

也就是在同一位置，不能出现两次相同的字符，因为第 2 次出现时，之前肯定已经针对这种情况，所有路线都已经走过了。

因此可以联想到使用集合，存储当前位置出现过的字符，如果重复，就可以直接跳过。

接下来我们看看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {

    char[] array;
    List<String> result = new LinkedList<>();
    public String[] permutation(String s) {
        array = s.toCharArray();
        // 回溯
        backtrack(0);
        // 赋值给数组
        String[] resultArray = new String[result.size()];
        int index = 0;
        for (String str : result) {
            resultArray[index] = str;
            index++;
        }
        return resultArray;
    }

    private void backtrack(int index) {
        // 如果是最后一个位置，就可以添加进result中
        if (index == array.length - 1) {
            StringBuilder sb = new StringBuilder();
            for (char temp : array) {
                sb.append(temp);
            }
            result.add(sb.toString());
            return;
        }

        Set<Character> set = new HashSet<>();
        for (int i = index; i < array.length; i++) {
            // 保证不会重复
            if (set.contains(array[i])) {
                continue;
            }
            set.add(array[i]);
            // 交换两者的位置
            swap(index, i);
            // 固定下一个位置，继续寻找
            backtrack(index + 1);
            // 还原两者的位置
            swap(i, index);
        }
    }

    private void swap(int index, int newIndex) {
        char temp = array[index];
        array[index] = array[newIndex];
        array[newIndex] = temp;
    }
}

提交OK。

分析一下复杂度：

  • 时间复杂度 O(N!) ： 这个比较好理解，长度为 N 的字符串，需要计算的次数是： N * (N - 1) * (N - 2) * ... * 2 * 1，结果也就是 N! 。
  • 空间复杂度 O(N^2) ： 需要借助的额外空间，也就是那个保证不会重复所使用到的set，它所存储的总量，最差情况下，长度为 N 的字符串中，所有字符各不相同，也就需要 N + (N - 1) + (N - 2) * ... * 2 * 1，结果也就是 N^2。

java 优化

针对上面代码中出现的 char[] 转 String，可以使用String.valueOf(char[])方法进行优化，因为该方法，最终会使用System.arrayCopy方法，该方法属于native方法，更加高效。

至于最终，将 list 转 array 的过程，可以用list.toArray(String[])做写法上的简化，性能上倒并没有什么提升。

优化后的代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {

    char[] array;
    List<String> result = new LinkedList<>();
    public String[] permutation(String s) {
        array = s.toCharArray();
        // 回溯
        backtrack(0);
        // 赋值给数组
        return result.toArray(new String[result.size()]);
    }

    private void backtrack(int index) {
        // 如果是最后一个位置，就可以添加进result中
        if (index == array.length - 1) {
            result.add(String.valueOf(array));
            return;
        }

        Set<Character> set = new HashSet<>();
        for (int i = index; i < array.length; i++) {
            // 保证不会重复
            if (set.contains(array[i])) {
                continue;
            }
            set.add(array[i]);
            // 交换两者的位置
            swap(index, i);
            // 固定下一个位置，继续寻找
            backtrack(index + 1);
            // 还原两者的位置
            swap(i, index);
        }
    }

    private void swap(int index, int newIndex) {
        char temp = array[index];
        array[index] = array[newIndex];
        array[newIndex] = temp;
    }
}

继续优化

其实到了，如果想进一步优化的话，可以针对 list 转 array 这里。

因为我们使用的是 LinkedList，内部存储的 String 对象在物理上是不连续的，在最后遍历时会相对比较耗时。

如果我们一开始就可以求出所有该字符串所能获得的所有不重复字符串的总个数的话，就可以提前构造一个 array，不需要在最后又遍历一次 list 了。

那么如何求出有重复字符的所有排列呢？假设是字符串aabbc，其求法为：

  1. 假设先排 a ，一共 5 个位置，选 2 个位置，C(5, 2) = (5 * 4) / (2 * 1) = 10。
  2. 再排 b ，剩下 3 个位置里，选 2 个位置，C(3, 2) = (3 * 2) / (2 * 1) = 3。
  3. 最后排 c ，剩下 1 个位置里，选 1 个位置，C(1, 1) = 1。
  4. 综上，一共有10 * 3 * 1 = 30种排列。

接下来看看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class Solution {

    char[] array;
    String[] result;
    int resultIndex = 0;
    public String[] permutation(String s) {
        array = s.toCharArray();
        // 求出一共有多少种可能
        int totalCount = calculate();
        result = new String[totalCount];
        // 回溯
        backtrack(0);
        // 赋值给数组
        return result;
    }

    private int calculate() {
        // 各字符出现的次数，默认只会出现26个英文字母
        int[] countArray = new int[26];
        for (char temp : array) {
            countArray[temp - 'a'] += 1;
        }
        // 统计总次数
        int length = array.length;
        int totalCount = 1;
        for (int count : countArray) {
            if (count == 0) {
                continue;
            }
            // 求排列
            totalCount *= cc(length, count);
            length -= count;
        }
        return totalCount;
    }

    private int cc(int total, int count) {
        // 如果count超过total的一半，则换成 (total - count)，因为在排列中，C(5, 4) = C(5, 1)
        if (count > total / 2) {
            count = total - count;
        }
        // 分别求分子、分母
        int result = 1;
        int result1 = 1;
        for (int i = 0; i < count; i++) {
            result *= (total - i);
            result1 *= (count - i);
        }
        return result / result1;
    }

    private void backtrack(int index) {
        // 如果是最后一个位置，就可以添加进result中
        if (index == array.length - 1) {
            result[resultIndex++] = String.valueOf(array);
            return;
        }

        // 默认只会出现26个英文字母
        boolean[] exists = new boolean[26];
        for (int i = index; i < array.length; i++) {
            // 保证不会重复
            if (exists[array[i] - 'a']) {
                continue;
            }
            exists[array[i] - 'a'] = true;
            // 交换两者的位置
            swap(index, i);
            // 固定下一个位置，继续寻找
            backtrack(index + 1);
            // 还原两者的位置
            swap(i, index);
        }
    }

    private void swap(int index, int newIndex) {
        char temp = array[index];
        array[index] = array[newIndex];
        array[newIndex] = temp;
    }
}

提交OK，其执行时间最短，因此认为优化是有效的。

总结

以上就是这道题目我的解答过程了，不知道大家是否理解了。本题主要在于对回溯的理解，优化时可以结合 java 特性，以及排列的一些知识。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。

https://death00.github.io/

公众号：健程之道

健健 wechat
欢迎您扫一扫上面的微信公众号，订阅我的博客！
如果您感觉文章不错，也愿意支持一下作者的话